package algo;

import model.tsp.Problem;
import model.tsp.Solution;
import util.CheckUtils;
import util.PrinterUtils;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;


/**
 * 3-opt
 * https://github.com/ozanyerli/tsp3opt/blob/main/tsp3opt.c#L258
 */
public class LocalSearch3opt extends LocalSearch {


    public LocalSearch3opt(Problem problem) {
        super(problem);
    }

    @Override
    public void solve() {
        Solution initSolution = initial();
        PrinterUtils.printTspResult("local search 3opt init", initSolution);
        Solution finalSolution = improve(initSolution);
        PrinterUtils.printTspResult("local search 3opt final", finalSolution);
        CheckUtils.check(finalSolution, distance);
    }


    @Override
    protected Solution improve(Solution solution) {
        int n = solution.length();
        int[] path = new int[n];
        for (int i = 0; i < n; i++) {
            path[i] = solution.getPermutation().get(i);
        }

        int a, b, c, d, e, f;
        boolean improve = true;
        while (improve) {
            improve = false;
            for (int i = 0; i < n - 5; i++) {
                a = path[i];
                b = path[(i + 1) % n];
                for (int j = i + 2; j < n - 3; j++) {
                    c = path[j];
                    d = path[(j + 1) % n];
                    for (int k = j + 2; k < n - 1; k++) {
                        e = path[k];
                        f = path[(k + 1) % n];

                        int bestCase = bestMove(a, b, c, d, e, f);
                        // Calculate the gain for each case
                        if (bestCase != 0) { // Make the move if a shorter tour is possible
                            makeMove(path, bestCase, i, j, k, n);
                            improve = true;
                            break;
                        }
                    }
                    if (improve) {
                        break;
                    }
                }
                if (improve) {
                    break;
                }
            }
        }

        repair(path);

        List<Integer> bestIndividual = new ArrayList<>();
        Arrays.stream(path).forEach(bestIndividual::add);
        int bestValue = calculateFitness(bestIndividual);
        return new Solution(bestIndividual, bestValue);
    }

    // Finds the case that results in maximum length gain
    private int bestMove(int a, int b, int c, int d, int e, int f) {
        int[] gains = new int[8];

        gains[0] = 0;

        gains[1] = distance[a][e] + distance[b][f] - distance[a][b] - distance[e][f];

        gains[2] = distance[c][e] + distance[d][f] - distance[c][d] - distance[e][f];

        gains[3] = distance[a][c] + distance[b][d] - distance[a][b] - distance[c][d];

        int deletedEdges = distance[a][b] + distance[c][d] + distance[e][f];

        gains[4] = distance[a][c] + distance[b][e] + distance[d][f] - deletedEdges;

        gains[5] = distance[a][e] + distance[d][b] + distance[c][f] - deletedEdges;

        gains[6] = distance[a][d] + distance[e][c] + distance[b][f] - deletedEdges;

        gains[7] = distance[a][d] + distance[e][b] + distance[c][f] - deletedEdges;

        int maxGain = 0;
        int bestCase = 0;
        int i;
        for (i = 1; i < 8; i++) {
            if (gains[i] < 0 && gains[i] < maxGain) {
                bestCase = i;
                maxGain = gains[i];
            }
        }

        return bestCase;
    }

    // Reverses a segment between two cities
    private void reverse(int[] path, int start, int end, int n) {
        int half = ((n + end - start + 1) % n) / 2;

        int left = start;
        int right = end;
        int temp;

        int i;
        for (i = 1; i < half + 1; i++) {
            temp = path[right];
            path[right] = path[left];
            path[left] = temp;

            left = (left + 1) % n;
            right = (n + right - 1) % n;
        }
    }

    // Changes the tour with reversing the segments, depending on the case
    private void makeMove(int[] path, int bestCase, int i, int j, int k, int n) {

        if (bestCase == 1) {
            reverse(path, (k + 1) % n, i, n);

        } else if (bestCase == 2) {
            reverse(path, (j + 1) % n, k, n);

        } else if (bestCase == 3) {
            reverse(path, (i + 1) % n, j, n);

        } else if (bestCase == 4) {
            reverse(path, (j + 1) % n, k, n);
            reverse(path, (i + 1) % n, j, n);

        } else if (bestCase == 5) {
            reverse(path, (k + 1) % n, i, n);
            reverse(path, (i + 1) % n, j, n);

        } else if (bestCase == 6) {
            reverse(path, (k + 1) % n, i, n);
            reverse(path, (j + 1) % n, k, n);

        } else if (bestCase == 7) {
            reverse(path, (k + 1) % n, i, n);
            reverse(path, (i + 1) % n, j, n);
            reverse(path, (j + 1) % n, k, n);
        }
    }

    // 修复路径，从0开始
    private void repair(int[] path) {
        while (path[0] > 0) {
            int temp = path[0];
            for (int i = 1; i < path.length; i++) {
                path[i - 1] = path[i];
            }
            path[path.length - 1] = temp;
        }
    }
}
